package leetcode.backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 陈正龙
 * @date 2022/3/15 19:57
 * 全排列
 * 给一个 数组 [1,2,3] 输出其全排列 1,2,3  1,3,2  2,1,3  2,3,1   3,1,2  3,2,1
 */
public class _46 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3};
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        boolean[] isUsed = new boolean[nums.length];
        dfs(res, path, isUsed, nums);

        System.out.println("res = " + res);

    }

    static void dfs(List<List<Integer>> res, Deque<Integer> path, boolean[] isUsed, int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!isUsed[i]) {
                path.push(nums[i]);
                isUsed[i] = true;
                dfs(res, path, isUsed, nums);
                isUsed[i] = false;
                path.pop();
            }
        }
    }

}
